package com.cet.algorithm.动态规划.目标和;

/**
 * @program: cet-practice
 * @description: 目标和
 * @author: 陈恩涛
 * @create: 2023-08-03 15:49
 **/
public class Lc494 {

    public int findTargetSumWays(int[] nums, int target) {
        // left: plus collection
        // right: minus collection
        // left - right = target      left + right = sum
        // left = (target + sum) / 2

        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
        }

        if((target + sum) % 2 != 0){
            return 0;
        }

        if(Math.abs(target)> sum){
            return 0;
        }

        int x = (target + sum) / 2;

        int[] dp = new int[x + 1];

        // dp[j] 装满容量为j的背包的不同方法数
        // dp[j] += dp[j - nums[i]]
        // dp[0] = 0;
        for(int i = 0; i < nums.length; i++){
            for(int j = x; j >= nums[i]; j--){
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[x];
    }

    public static void main(String[] args) {
        Lc494 lc494 = new Lc494();
        System.out.println(lc494.findTargetSumWays(new int[]{1, 1, 1, 1, 1}, 3));
    }
}
